package com.kevinkk.string;

/**
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 */

/**
 * 方法1️⃣：
 * 如果字符串 s 能够被子串重复构成，那么字符串 s + s 一定能够被字符串 s 构成
 * 那么从 s + s 中去除首尾元素，一定能找到字符串 s
 */

/**
 * 方法2️⃣：
 * 借助 KMP 算法中的 next 数组
 * 如果一个字符串能够被重复子串构成，那么这个 最长重复子串 就是 字符串 除去 最长公共前缀 的部分
 */

public class RepeatedSubstringPattern {
    class Solution1 {
        public boolean repeatedSubstringPattern(String s) {
            StringBuilder sb = new StringBuilder(s);
            sb.append(s);
            sb.deleteCharAt(0);
            sb.deleteCharAt(sb.length() - 1);
            return sb.toString().contains(s);
        }
    }

    class Solution2 {
        public boolean repeatedSubstringPattern(String s) {
            int[] next = getNext(s.toCharArray());
            int len = s.length();
            return next[len - 1] > 0 && len % (len - next[len - 1]) == 0;
        }

        private int[] getNext(char[] c) {
            int[] next = new int[c.length];
            int j = 0;
            next[0] = 0;
            for (int i = 1; i < c.length; i++) {
                while (j > 0 && c[i] != c[j])
                    j = next[j - 1];
                if (c[i] == c[j])
                    j++;
                next[i] = j;
            }
            return next;
        }
    }
}
